package dtst;

import java.util.HashMap;
import java.util.Map;

public class LRUCache{
    class Node{
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    private Node dummy = new Node(-1,-1);
    private Integer capacity;
    private Map<Integer,Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        dummy.next = dummy;
        dummy.pre = dummy;
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = getNode(key);
        return node==null?-1:node.value;
    }

    public void put(int key, int value) {
        Node node = getNode(key);
        if(node!=null){
            node.value = value;
            return;
        }
        node = new Node(key,value);
        keyToNode.put(key,node);
        putFront(node);
        if(keyToNode.size()>capacity){
            Node back = dummy.pre;
            remove(back);
            keyToNode.remove(back.key);
        }
    }

    public Node getNode(int key){
        Node node = keyToNode.getOrDefault(key,null);
        if(node==null) return null;
        remove(node);
        putFront(node);
        return node;
    }


    public void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void putFront(Node node){
        node.next = dummy.next;
        node.pre = dummy;
        dummy.next.pre = node;
        dummy.next = node;
    }

}